//#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//#include<stdlib.h>
//
//struct ListNode
//{
//    int val;
//    struct ListNode* next;
//};
//
//
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//
//    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
//    newhead->next = NULL;
//    struct ListNode* l1 = list1;
//    struct ListNode* l2 = list2;
//    struct ListNode* tail = newhead;
//
//    if (list1 == NULL) return list2;
//    if (list2 == NULL) return list1;
//
//    while (l1 != NULL && l2 != NULL)
//    {
//        if (l1->val <= l2->val)
//        {
//            tail->next = l1;
//            tail = tail->next;
//            l1 = l1->next;
//            tail->next = NULL;
//        }
//        else
//        {
//            tail->next = l2;
//            tail = tail->next;
//            l2 = l2->next;
//            tail->next = NULL;
//        }
//    }
//    if (l1 == NULL) tail->next = l2;
//    if (l2 == NULL) tail->next = l1;
//    tail = newhead->next;
//    free(newhead);
//    return tail;
//}
//
//
//int main()
//{
//    struct ListNode* a1 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* a2 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* a3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* a4 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* a5 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* a6 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    a1->val = 1;
//    a2->val = 2;
//    a3->val = 4;
//    a4->val = 1;
//    a5->val = 3;
//    a6->val = 4;
//    struct ListNode* head1 = a1;
//    struct ListNode* head2 = a4;
//    a1->next = a2;
//    a2->next = a3;
//    a3->next = NULL;
//
//    a4->next = a5;
//    a5->next = a6;
//    a6->next = NULL;
//    struct ListNode* ret = mergeTwoLists(head1, head2);
//
//
//    return 0;
//}